package com.zp.self.module.level_4_算法练习.脑筋急转弯;

/**
 * @author By ZengPeng
 */
public class 力扣_55_跳跃游戏 {
    static int sheng =0;
    static int 次数 =0;
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_55_跳跃游戏().canJump(new int[]{0}));
        System.out.println(new 力扣_55_跳跃游戏().canJump(new int[]{0,1,2,3,4,5,0}));
        System.out.println(new 力扣_55_跳跃游戏().canJump(new int[]{5,4,3,2,1,0,1}));
        System.out.println(new 力扣_55_跳跃游戏().canJump(new int[]{2,3,1,1,4}));
        System.out.println(new 力扣_55_跳跃游戏().canJump(new int[]{3,2,1,0,4}));
        System.out.println(new 力扣_55_跳跃游戏().canJump(new int[]{8,2,4,4,4,9,5,2,5,8,8,0,8,6,9,1,1,6,3,5,1,2,6,6,0,4,8,6,0,3,2,8,7,0,5,1,7,0,3,4,8,3,5,9,0,4,0,1,0,5,9,2,0,7,0,2,1,0,8,2,5,1,2,3,9,7,4,7,0,0,1,8,5,6,7,5,1,9,9,3,5,0,7,5}));
    }

    /**
    题目：给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
     数组中的每个元素代表你在该位置可以跳跃的最大长度。
     判断你是否能够到达最后一个下标。

     示例 1：
     输入：nums = [2,3,1,1,4]
     输出：true
     解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

     示例 2：
     输入：nums = [3,2,1,0,4]
     输出：false
     解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

    分析：【P 💜💜💜】
       1.回溯法: 遍历每一种情况，一步一步的跳，效率低啊 【可能会超时啊】
                -- 执行用时：47 ms, 在所有 Java 提交中击败了16%的用户
                优化：用位图记录行不通的节点boolean[],提升效率，先走大的踏步，提前知道后面的行不行
        2.贪心算法，我当前能走的范围中，找到最大的一步
                    再在最大的这一步范围内找，最大的一步
                --执行用时：83 ms, 在所有 Java 提交中击败了12.78%的用户
        大神解法，从后向前，判断前面的值能否到大新的终点  【我其实想过从后向前，但没想到这么牛逼, 时间：O(n)】
                --执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户

    边界值 & 注意点：
       1.
     **/
    public boolean canJump(int[] nums) {
        // 大神解法，从后向前，判断前面的值能否到大新的终点
        int end = nums.length-1;
        for (int i = nums.length-2; i >=0; i--) {
            if(nums[i]+i>=end){
                end=i;
            }
        }
        return end==0;
        //2.贪心算法
        /*int start =0;
        while (start+nums[start]<nums.length-1){
            int maxIndex = -1;
            for (int i = start+1; i <= start+nums[start] ; i++) {
                if(nums[i]==0) continue;
                if(maxIndex ==-1  || nums[i]+i > nums[maxIndex]+maxIndex){
                    maxIndex = i;
                }
            }
            if(maxIndex==-1) return false;
            start = maxIndex;
        }
        return true;*/


        //1.回溯法
/*        boolean[] block = new boolean[nums.length];//当前节点是否阻塞
        return recursive(nums,0,block);*/
    }

    /**
    *  递归3步曲：
     *   1.单步操作
     *   2.终止条件
     *   3.返回值
    * @param nums 数组
    * @param index 当前节点
    * @param block 记录通畅，减少执行时间
    **/
    private boolean recursive(int[] nums, int index, boolean[] block) {
        if(nums[index]==0)return false;
        if(index+nums[index]>=nums.length-1) return true;
        int maxIndex = index+nums[index];//最大位移值
        for (int i = maxIndex; i >index; i--) {
            if(block[i]) {
                continue;//这个值往下走行不通
            }
            boolean recursive = recursive(nums, i, block);

            if(recursive) return true;
            else block[i] = true;
        }
        return false;
    }
}
